package Top200;

import java.util.LinkedList;

/**
 * @author zhangmin
 * @create 2022-02-23 11:49
 * 回溯
 */
public class getPermutation60 {
    LinkedList<String> res=new LinkedList<>();
    int k;
    boolean[] visted;
    void backtrack(int n,int index,StringBuffer path){
        if (k<0) return;
        if (index==n){
            res.add(path.toString());
            k--;
            return;
        }
        for (int i = 1; i <= n ; i++) {
            if (visted[i]) continue;
            path.append(i);
            visted[i]=true;
            backtrack(n,index+1,path);
            visted[i]=false;
            path.deleteCharAt(index);
        }
    }
    public String getPermutation(int n, int k) {
        this.k=k;
        visted=new boolean[n+1];
        backtrack(n,0,new StringBuffer());
        return res.get(k-1);
    }
}
